import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author ZhangCuirong
 * @Date 2025/9/15 21:10
 * @description:
 *
 */
/**
 * @Author ZhangCuirong
 * @Date 2025/9/15 21:10
 * @description:
 */


public class Solution679 {
    //这种是错的
//    你的代码思路是：从 1 个初始数字开始，连续用 “当前结果 ±×÷ 下一个未使用数字”，本质是1 个数字与其他 3 个数字的顺序运算（如 ((a op1 b) op2 c) op3 d），但这忽略了 “24 点” 的关键场景 ——任意两个数字先组合运算（如 (a op1 b) op2 (c op3 d) 或 a op1 (b op2 (c op3 d)) 等）。
//
//    例如，对于 1,3,4,6，正确解法是 6 ÷ (1 - 3/4) = 24，但你的代码无法实现 “3/4” 这个子运算（因为你的逻辑是 “用当前结果运算下一个数字”，无法先对两个未使用的数字运算）。

//    public void backtrack(int[] cards, boolean[] visited, LinkedList<Object> path, double res) {
//        if (path.size() == 7) {
//            if (Math.abs(res - TARGET) < EPSILON) {
//                isJudgeRes = true;
//                System.out.println(path);
//                return;
//            }
//        }
//
//        for (int i = 0; i < cards.length; i++) {
//            if (!visited[i]) {
//                visited[i] = true;
//                path.add('+');
//                path.add(cards[i]);
//                backtrack(cards, visited, path, res + cards[i]);
//                path.removeLast();
//                path.removeLast();
//
//
//                path.add('-');
//                path.add(cards[i]);
//                backtrack(cards, visited, path, res - cards[i]);
//                path.removeLast();
//                path.removeLast();
//
//                path.add('*');
//                path.add(cards[i]);
//                backtrack(cards, visited, path, res * cards[i]);
//                path.removeLast();
//                path.removeLast();
//
//                path.add('/');
//                path.add(cards[i]);
//                backtrack(cards, visited, path, res / cards[i]);
//                path.removeLast();
//                path.removeLast();
//                visited[i] = false;
//            }
//
//        }
//    }
    public static class NumExpr {
        double num;
        String expression;

        public NumExpr(double num, String expression) {
            this.num = num;
            this.expression = expression;
        }
    }

    private static final double TARGET = 24.0;
    //浮点数比较误差阈值
    private static final double EPSILON = 1e-6;
    //用于存储找到的结果表达式

    private String resultExpression;


    public boolean judgePoint24(int[] cards) {
        resultExpression = null;
        List<NumExpr> nums = new ArrayList<>();
        for (int card : cards) {
            nums.add(new NumExpr(card, String.valueOf(card)));
        }
        backtrack(nums);
        return resultExpression != null;

    }

    public boolean backtrack(List<NumExpr> nums) {
        // 终止条件：只剩1个数字，判断是否接近24
        if (nums.size() == 1) {
            if (Math.abs(nums.get(0).num - TARGET) < EPSILON) {
                resultExpression = nums.get(0).expression;
                return true;
            }
            return false;
        }

        // 遍历所有两两组合（i < j 避免重复，后续处理顺序相关的运算）
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                // 获取当前选中的两个数字
                NumExpr a = nums.get(i);
                NumExpr b = nums.get(j);
                // 生成“新数字列表”：移除a和b，加入运算结果
                List<NumExpr> newNums = new ArrayList<>();
                for (int k = 0; k < nums.size(); k++) {
                    if (k != i && k != j) {
                        newNums.add(nums.get(k));
                    }
                }
                // 尝试4种运算（注意减法和除法的双向性）
                //1. 加法
                newNums.add(new NumExpr(a.num + b.num, "(" + a.expression + "+" + b.expression + ")"));
                if (backtrack(newNums)) return true;
                // 回溯：移除当前运算结果
                newNums.remove(newNums.size() - 1);

                //2.减法
                newNums.add(new NumExpr(a.num - b.num, "(" + a.expression + "-" + b.expression + ")"));
                if (backtrack(newNums)) return true;
                newNums.remove(newNums.size() - 1);

                newNums.add(new NumExpr(b.num - a.num, "(" + b.expression + "-" + a.expression + ")"));
                if (backtrack(newNums)) return true;
                newNums.remove(newNums.size() - 1);

                //3.乘法
                newNums.add(new NumExpr(a.num * b.num, "(" + a.expression + "*" + b.expression + ")"));
                if (backtrack(newNums)) return true;
                newNums.remove(newNums.size() - 1);

                //4.除法
                if (Math.abs(b.num) > EPSILON) {
                    newNums.add(new NumExpr(a.num / b.num, "(" + a.expression + "/" + b.expression + ")"));
                    if (backtrack(newNums)) return true;
                    newNums.remove(newNums.size() - 1);
                }
                if (Math.abs(a.num) > EPSILON) {
                    newNums.add(new NumExpr(b.num / a.num, "(" + b.expression + "/" + a.expression + ")"));
                    if (backtrack(newNums)) return true;
                    newNums.remove(newNums.size() - 1);
                }

            }
        }
        return false;
    }

    public String getExpression() {
        return this.resultExpression;
    }

    public static void main(String[] args) {
        Solution679 solution = new Solution679();
        int[] test1 = {4, 1, 6, 7};
        if (solution.judgePoint24(test1)) {
            System.out.println("测试用例1: " + solution.getExpression() + " = 24");
        } else {
            System.out.println("测试用例1: 无法得到24");
        }

        int[] test2 = {1, 3, 4, 6};
        if (solution.judgePoint24(test2)) {
            System.out.println("测试用例2: " + solution.getExpression() + " = 24");
        } else {
            System.out.println("测试用例2: 无法得到24");
        }

        int[] test3 = {1, 2, 1, 2};
        if (solution.judgePoint24(test3)) {
            System.out.println("测试用例3: " + solution.getExpression() + " = 24");
        } else {
            System.out.println("测试用例3: 无法得到24");
        }

        int[] test4 = {4, 1, 8, 7};
        if (solution.judgePoint24(test4)) {
            System.out.println("测试用例4: " + solution.getExpression() + " = 24");
        } else {
            System.out.println("测试用例4: 无法得到24");
        }
    }
}
